package divide;

/**
 * @author chenyang
 */
public class MergeSort {

    public static void sort(int[] randomArray) {
        sort(randomArray, 0, randomArray.length - 1);
    }

    public static void sort(int[] array, int L, int R) {
        if (L >= R) {
            return;
        }
        int M = (L + R) / 2;
        sort(array, L, M);
        sort(array, M + 1, R);
        merge1(array, L, R, M);
    }

    private static void merge(int[] array, int L, int R, int M) {
        int[] result = new int[R - L + 1];
        int i = 0;
        int r = M + 1;
        int l = L;
        while (l <= M && r <= R) {
            if (array[l] <= array[r]) {
                result[i++] = array[l++];
            } else {
                result[i++] = array[r++];
            }
        }
        while (l <= M) {
            result[i++] = array[l++];
        }
        while (r <= R) {
            result[i++] = array[r++];
        }

        for (int j = 0; j < result.length; j++) {
            array[L + j] = result[j];
        }
    }

    private static void merge1(int[] array, int L, int R, int M) {
        int[] A = new int[M - L + 1];
        int[] B = new int[R - M];
        for (int i = 0; i < A.length; i++) {
            A[i] = array[L + i];
        }
        for (int i = 0; i < B.length; i++) {
            B[i] = array[M + i + 1];
        }

        int l = L, j = 0, k = 0;
        while (j < A.length && k < B.length) {
            if (A[j] <= B[k]) {
                array[l++] = A[j++];
            } else {
                array[l++] = B[k++];
            }
        }
        while (j < A.length) {
            array[l++] = A[j++];
        }
        while (k < B.length) {
            array[l++] = B[k++];
        }
    }

    public static void swap(int[] array, int i, int j) {
        int value = array[i];
        array[i] = array[j];
        array[j] = value;
    }
}
